package com.cdream.basic.algorithm.leetcode.linkedlist;

import java.util.LinkedList;

/**
 * @author cdream
 * @date 6/13/21
 */
public class Question143 {
    public static void main(String[] args) {
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        new Question143().reorderList(node1);
    }

    public void reorderList(ListNode head) {
        LinkedList<ListNode> listNodes = new LinkedList<>();
        ListNode cur = head;
        int count = 0;
        while (cur != null) {
            count++;
            listNodes.push(cur);
            cur = cur.next;
        }
        int i = count / 2;
        cur = head;
        for (int j = 0; j < i; j++) {
            ListNode p = listNodes.poll();
            ListNode peek = listNodes.peek();
            if (peek != null) {
                peek.next = null;
            }
            p.next = cur.next;
            cur.next = p;
            cur = cur.next.next;
        }
    }
}
